class Solution {
public:
    int numTrees(int n) {
        vector<int> dp(n + 1);
        dp[0] = 1;
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= i; j++)
                dp[i] += dp[j - 1] * dp[i - j];
        return dp[n];
    }
};
class Solution {
public:
    int combinationSum4(vector<int>& nums, int target) {
        int n = nums.size();
        vector<double> dp(target + 1);
        dp[0] = 1;
        for (int i = 1; i <= target; i++)
            for (auto e : nums)
                if (i >= e)
                    dp[i] += dp[i - e];
        return dp[target];

    }
};